// 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

// 示例：

// 输入: S = "ADOBECODEBANC", T = "ABC"
// 输出: "BANC"
// 说明：

// 如果 S 中不存这样的子串，则返回空字符串 ""。
// 如果 S 中存在这样的子串，我们保证它是唯一的答案。

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution1 {
public:
    string minWindow(string s, string t) {
        string res{};
        unordered_map<char, int> letterCount{};
        int left{0};
        int count{0};
        int minLen(INT_MAX);
        for (char c : t) {
            ++letterCount[c];
        }
        int m = s.size();
        int n = t.size();
        for (int i{0}; i < m; ++i) {
            if (--letterCount[s[i]] >= 0) ++count;
            while (count == n) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    res = s.substr(left, minLen);
                }
                if (++letterCount[s[left]] > 0) --count;
                ++left;
            }
        }
        return res;
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> letterCount(128, 0); // 字母表，统计t中每个字母的个数
        int left{0};
        int count{0};
        int minLeft{-1};
        int minLen{INT_MAX};
        for (char c : t) ++letterCount[c];
        int m = s.size();
        int n = t.size();
        for (int i{0}; i < m; ++i) {
            if (--letterCount[s[i]] >= 0) ++count;
            while (count == n) {
                if (minLen > i - left + 1) { // 最短长度
                    minLen = i - left + 1;
                    minLeft = left;
                }
                if (++letterCount[s[left]] > 0) --count;
                ++left;
            }
        }
        return minLeft == -1 ? "" : s.substr(minLeft, minLen);
    }
};